#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct Node
{
    int pos,val;
    Node(int pos=0,int val=0):pos(pos),val(val){}
};

Node q[150005];
int n,m,_;
int x,y;
ll a[150005],ans;

int main()
{
    freopen("clear.in","r",stdin);
    freopen("clear.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    cin>>n>>m>>_;

    for(int i=1;i<=n;i++)
        cin>>a[i];

    if(n>5000)
    {
        for(int i=m+1;i<=n;i++)
            a[i]+=a[i-m];

        while(_--)
        {
            int l,r;
            cin>>l>>r;

            l+=(r-l)%m;
            if(l<=m)
                cout<<a[r]<<'\n';
            else
                cout<<a[r]-a[l-m]<<'\n';
        }
        
        return 0;
    }

    while(_--)
    {
        int l,r;
        cin>>l>>r;

        ans=a[l];
        q[x=y=1]=Node(l,a[l]);
        for(int i=l+1;i<=r;i++)
        {
            int tp=a[i]-a[i-1];
            if(x<=y&&q[x].pos+m==i)
                tp+=q[x++].val;

            while(tp<0)
            {
                if(q[x].val+tp<=0)
                    tp+=q[x++].val;
                else
                    q[x].val+=tp,tp=0;
            }

            if(tp>0)
            {
                ans+=tp;
                q[++y]=Node(i,tp);
            }
        }

        cout<<ans<<'\n';
    }

    return 0;
}